package codeRandomThoughts.Test84柱状图中最大的矩形;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;

//用单调栈求左边第一个比自己小的位置和右边第一个比自己小的位置
//和接雨水那题非常相似
public class Solution2 {
    public static int largestRectangleArea(int[] heights) {
        //准备工作 加上两个边界值
        List<Integer> list = new ArrayList<>();
        list.add(0);
        for (int height : heights) {
            list.add(height);
        }
        list.add(0);
        int result = 0;
        Stack<Integer> s = new Stack<>();
        s.push(0);
        for (int i = 1; i < list.size(); i++) {
            while (list.get(i) < list.get(s.peek())) {
                int mid = s.pop();
                int w = i - s.peek() - 1;
                int h = list.get(mid);
                result = Math.max(result, w * h);
            }
            s.push(i);
        }
        return result;
    }

    public static void main(String[] args) {
        int[] heights = {2, 1, 5, 6, 2, 3};
        System.out.println(largestRectangleArea(heights));
    }
}
